import java.util.LinkedList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        int m = ss.length(), n = pp.length(), count = 0;
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        int[] hashS = new int[26]; int[] hashP = new int[26];
        List<Integer> ret = new LinkedList<>();

        //把所有的p加入到哈希表中
        for(char x : p) {
            hashP[x - 'a'] += 1;
        }
        //开始遍历
        for(int left = 0, right = 0; right < m; right++) {
            //进窗口
            hashS[s[right] - 'a']++;
            //维护count,有效字符变量
            if(hashS[s[right] - 'a'] <= hashP[s[right] - 'a']) count++;
            //判断
            if(right - left + 1 == n) {
                // //检查两哈希表内的元素是否相同
                // if(check(hashS, hashP)) {
                //     ret.add(left);
                // }
                if(count == n) ret.add(left);
                //维护count,有效字符变量
                if(hashS[s[left] - 'a'] <= hashP[s[left] - 'a']) count--;
                //出窗口
                hashS[s[left++] - 'a']--;
            }
        }
        return ret;
    }
    // public boolean check(int[] hashS, int[] hashP) {
    //     for(int i = 0; i < 26; i++) {
    //         if(hashS[i] != hashP[i]) return false;
    //     }
    //     return true;
    // }
}